数学超苦手な文系エンジニアがAtCoder Beginner Contest 266に参加してみました

今泉大樹

2022.09.01

この記事は公開されてから1年以上経過しています。情報が古い可能性がありますので、ご注意ください。

こんにちは、AWS事業本部コンサルティング部に所属している今泉(@bun76235104)です。

皆さんはアルゴリズムと数学に強くなりたいですか？

私はなりたいです。

時間を見つけては、ちょこまかとAtCoderという競技プログラミングのサイトの過去問を解いたり、実際にコンテストに参加したりしています。

今回も2022/8/27に開催された AtCoder Beginner Contest 266 というコンテストに参加してみたので、その時の記録や自分がどう考えてどのようなコードを出したのかなどをご紹介させていただきます。

前置き・事前知識

AtCoderとは何か・どのようにして問題を解くのかといったことに関しては、以下の記事をご参照ください。

※ 本記事はあくまで私がAtCoderに参加した結果を記載しており、会社全体が私と同じレベルということではありませんことご承知おきください。

想定される読者の方について

私自身は高校時代から所属も脳の構造もゴリゴリの文系であり、数学をとても苦手としています。

いつまでも苦手意識を持っているのも嫌で、時間を見つけて競技プログラミングの学習を通してアルゴリズムと数学の学習を行なっています。 (仕事・家庭・他の分野の学習の都合で競技プログラミングのみにフルコミットすることはできない状況です)

そんな私の現在のレベルは下図でいうところの灰コーダー(一度でもコンテストに参加したらなれる)の上位レベルです。

atcoder_colors

(画像はe869120様のレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【初級編：競プロを始めよう】 - Qiitaより引用させていただいております)

以上を踏まえて、本記事を読んで何らかの学び・刺激を受けることができる方は以下に該当する方と思われます。

これから競技プログラミングを始めようとしている・始めたばかり
数学やアルゴリズムが苦手
周りのレベルの高さに挫折した・挫折しかけている
AtCoder Beginner ContestでC問題まで解くことを目標にしている
PythonでAtCoderを始めた・始めている
個人的に筆者を知っている・応援している(!?)

それ以外の方には特に見るべきポイントも無いと思われますのでご了承ください。

コンテスト参加結果

毎回の目標としているC問題まで解くことができました。

レートも271 => 312 と上げることができました。

atcoder_bun913_20220827_rate

それぞれの問題の内容とコンテスト中のコードと何を考えていたかをまとめてみます。

A問題 Middle Letter

英小文字からなる長さが奇数の文字列 S が与えられます。S の中央の文字を出力してください。

私が提出したコードがこちらです(1分25秒程で提出)

S = input()
cent = len(S) // 2
print(S[cent])

入力される文字列が奇数文字ということがわかっているので、頭の中で以下のように実際の文字を考えてみました

input: abc
output: b(2文字目。添字だと1)

input:abcde
output: c(3文字名。添字だと2)

Pythonは // で除算結果を切り捨てた結果を計算してくれるので 3//2 だと 1 が、 5//2 だと 2 が返されます。

そのまま出力された数値を添字に使って出力すればOKでした。

B問題 Modulo Number

−10 ** 18 以上 10 ** 18以下の整数Nが与えられます。以下の条件を満たす 0 以上 998244353 未満の整数 x を求めてください。なお、答えが一意に定まることが証明できます。

N−x は 998244353 の倍数

私が提出したコードがこちらです(2分30秒程で提出)

N = int(input())
ans = (N % 998244353)
print(ans)

答えを書くとこれだけなのですが、個人的にこれがパッと書けるようになっていることに少しばかりの成長を感じています。

以下のような考えをしていました

N-x が 998244353 の倍数になることがわかっている
N から何を引いたら 998244353 の倍数になるかということか
N - x = a * 998244353 ということだよね(aは整数)
余りを考えるだけじゃないだろうか
- a * 998244353 の部分は 998244353 で割ったら確実に余りが0になる
- Nを 998244353 で割ったあまりが出せれば、あまりの分だけ引き算をしてあげれば 998244353 の倍数になるはず
- N % 998244353　を求めれば良いだけか

実際の入力例からも考えてみます

入力例1: 998244354 % 998244353 は 1 になる。 998244354-1 が 998244353 の倍数になるのでOK
入力例2: -9982443534 % 998244353 は 998244349 となる。-9982443534-998244349 が 998244353 の倍数になるのでOK

解説 - AtCoder Beginner Contest 266を確認しましたが、考え方はこれで合っているようでした。

ちなみに私はゴリゴリの文系なので、AtCoderの学習を始める前であれば↓という考え方が出てこないか、時間がかかったと思います。

この問題で求められていることは、 N を 998244353 で割ったあまりを答えることです。

私の場合ですがこちらの「プログラマの数学第2版」の第3章「第3章剰余 ―― 周期性とグループ分け」を読むことで考え方が理解できるようになりましたので、解説を見てもピントこない方におすすめです!!

他にも余りの性質は面白く、よく出題されるているのを観測しています。

このような記事も見てみると面白いと思います。

C問題 Convex Quadrilateral

いやー・・・とても苦手な数学の問題ですね。

3回間違えましたが、何とか検索を駆使して答えを出すことができました。(出した答えは解説のやり方とは異なります)

四角形の各辺の角度を求めれば良いということで、それぞれの4点の座標の位置がわかっているのでベクトルか三角関数の問題かな？と思いました。

そうしたら以下のように2つのベクトルの成す角を求める参考記事が出てきたのでこちらを参考にいたしました

最終的に提出したコードがこちらです

import numpy as np
import math
 
A = np.array(list(map(int, input().split())))
B = np.array(list(map(int, input().split())))
C = np.array(list(map(int, input().split())))
D = np.array(list(map(int, input().split())))
 
def nasukaku(cent, left, right):
    vec1 = [left[0]-cent[0], left[1]-cent[1]]
    vec2 = [right[0]-cent[0], right[1]-cent[1]]
    absvec1 = np.linalg.norm(vec1)
    absvec2 = np.linalg.norm(vec2)
    inner = np.inner(vec1, vec2)
    cos_theta = inner/(absvec1*absvec2)
    theta = np.degrees(np.arccos(cos_theta))
    return theta
 
 
ABC = nasukaku(B, A, C)
BCD = nasukaku(C, B, D)
CDA = nasukaku(D, C, A)
DAB = nasukaku(A, D, B)
 
# print(ABC, BCD, CDA, DAB)
if ABC < 180 and BCD < 180 and CDA < 180 and DAB < 180:
    if math.isclose(ABC+BCD+CDA+DAB, 360.0) is False:
        print('No')
        exit()
print('Yes')

後で解説 - AtCoder Beginner Contest 266を見て気づいたのですが、ベクトルの外積を利用すればよかったようです。